class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        // this.tree = null;
        this.root = null;
    }
    //insert(key)
    insert(key) {
        //1.创建一个节点
        const newNode = new Node(key);
        //2.如果数时一个空树
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
    insertNode(node, newNode) {
        if (newNode.key > node.key) {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        } else {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode)
            }
        }
    }
    //search(key)
    //inOrderTraverse 中序遍历
    inOrderTraverse() {
        this.inOrderTraverseNode(this.root)
    }
    inOrderTraverseNode(node) {
        if (node === null) return;

        this.inOrderTraverseNode(node.left);
        console.log(node.key);
        this.inOrderTraverseNode(node.right);
    }
    //preOrderTraverse: 先序遍历
    preOrderTraverse() {
        this.preOrderTraverseNode(this.root)
    }
    preOrderTraverseNode(node) {
        if (node === null) return;

        console.log(node.key);
        this.preOrderTraverseNode(node.left);
        this.preOrderTraverseNode(node.right);
    }
    //postOrderTraverse 后序遍历
    postOrderTraverse() {
        this.postOrderTraverseNode(this.root);
    }
    postOrderTraverseNode(node) {
        if (node.key === null) return;

        this.postOrderTraverseNode(node.left);
        this.postOrderTraverseNode(node.right);
        console.log(node.key);
    }
    //min 返回最小值
    min() {
        if (this.root === null) return;
        let node = this.root;
        while (node.left !== null) {
            node = node.left;
        }
        return node.key;
    }
    //max 返回最大值
    max() {
        let node = this.root;
        while (node.right !== null) {
            node = node.right;
        }
        return node.key;
    }
    //search(key)搜索 存在返回true
    search(key) {
        let node = this.root;
        while (node !== null) {
            if (key > node.key) {
                node = node.right;
            } else if (key < node.key) {
                node = node.left;
            } else return true;
        }
        return false;
    }
    //remove(key) 
    remove(key) {
        //1.找到要删除的节点
        let current = this.root;
        let parent = null;
        let isLeftChild = true;
        //2.开始查找要删除的节点
        while (current.key !== key) {
            parent = current;
            if (key > current.key) {
                isLeftChild = false;
                current = current.right;
            } else {
                isLeftChild = true;
                current = current.left;
            }
            if (current === null) return false;
        }
        //3.找到我们的节点current和parent
        //情况一：删除的子节点是叶子结点(没有子结点) 
        if (current.left === null && current.right === null) {
            if (current === this.root) {
                this.root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        //情况二：删除的子结点只有一个分支结点
        else if (current.right === null) {//只有左子节点
            if (current === this.root) {
                this.root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left === null) {//只有右子节点
            if (current === this.root) {
                this.root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else {
            //1.获取后继节点
            let successor = this.getSuccessor(current);//获取到要删除的节点
            //2.判断是否是根节点
            if (current === this.root) {
                this.root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }


        return true;
    }

    //获取后继  实现删除
    getSuccessor(delNode) {
        //1.定义变量，来存储临时的节点
        let successerParent = delNode;
        let successer = delNode;
        let current = delNode.right;
        //2.寻找节点
        while (current !== null) {
            successerParent = successer;
            successer = current;
            current = current.left;
        }
        //3.如果后继节点不是删除节点的右节点
        if (successer != delNode.right) {
            successerParent.left = successer.right;
            successer.right = delNode.right;
        }
        return successer;
    }
}
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(6);
bst.insert(13);
bst.insert(12);
bst.insert(8);
bst.insert(10);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
// console.log(bst);
// console.log(bst.root.key);
bst.preOrderTraverse();
// console.log(bst.min());
console.log(bst);
// console.log(bst.search(25));